package leetcode_core.leetcode_7;

import sun.awt.image.ImageWatched;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年02月24日 21:49
 */
public class FindOrder {
    private boolean[] visited;
    private boolean[] onPath;
    private boolean hasCycle;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //1. 初始化常量
        visited = new boolean[numCourses];
        onPath = new boolean[numCourses];
        //2. 建图
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        //3. 遍历
        for(int i = 0;i<numCourses;i++){
            traverse(graph,i);
        }
        //4. 返回结果
        return !hasCycle;
    }

    /**
     * 定义依赖关系,也就是说:从map[i]->target
     * 其中i需要依赖于target
     * @param numCourses:有几门课
     * @param prerequisites:课的依赖关系
     * @return
     */
    private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites){
        //1. 初始化图
        List<Integer>[] graph = new LinkedList[numCourses];
        for(int i = 0;i<numCourses;i++){
            graph[i] = new LinkedList<>();
        }
        //2. 遍历关系表
        for (int[] prerequisite : prerequisites) {
            //学习[0]必须先学习[1]
            //那么也就是说[0]依赖于[1]
            int from = prerequisite[0];
            int to = prerequisite[1];
            graph[from].add(to);
        }
        return graph;
    }

    //遍历函数
    private void traverse(List<Integer>[] graph,int s){
        if(onPath[s]){
            hasCycle = true;
        }
        if(hasCycle || visited[s]){
            return;
        }
        visited[s] = true;
        onPath[s] =true;
        for (Integer t : graph[s]) {
            traverse(graph,t);
        }
        onPath[s] = false;
    }
}
